package com.c2b.algorithm.leetcode.hot100;

/**
 * <a href="https://leetcode.cn/problems/median-of-two-sorted-arrays/">寻找两个有序数组的中位数</a>
 * <p>给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。<br>算法的时间复杂度应该为 O(log (m+n)) 。</p>
 * <pre>
 * 示例 1：
 *      输入：nums1 = [1,3], nums2 = [2]
 *      输出：2.00000
 *      解释：合并数组 = [1,2,3] ，中位数 2
 *
 * 示例 2：
 *      输入：nums1 = [1,2], nums2 = [3,4]
 *      输出：2.50000
 *      解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * </pre>
 * <b>提示：</b>
 * <li>nums1.length == m</li>
 * <li>nums2.length == n</li>
 * <li>0 <= m <= 1000</li>
 * <li>0 <= n <= 1000</li>
 * <li>1 <= m + n <= 2000</li>
 * <li>-10^6 <= nums1[i], nums2[i] <= 10^6</li>
 *
 * @author c2b
 * @since 2022/4/29 15:08
 */
public class Hot004FindMedianSortedArrays_H {

    private Hot004FindMedianSortedArrays_H() {
    }

    /**
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     * <p>算法的时间复杂度应该为 O(log (m+n)) 。
     * <p>-------------------------------------------------
     * <p>输入：nums1 = [1,3], nums2 = [2]
     * <p>输出：2.00000
     * <p>解释：合并数组 = [1,2,3] ，中位数 2
     * <p>-------------------------------------------------
     * <p>输入：nums1 = [1,2], nums2 = [3,4]
     * <p>输出：2.50000
     * <p>解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
     * <p>-------------------------------------------------
     *
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 两个数组合并后的中位数
     * @author c2b
     * @since 2022/4/29 15:09
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int num1Len = nums1.length;
        int num2Len = nums2.length;
        int totalLength = num1Len + num2Len;
        if (num1Len == 0) {
            return totalLength % 2 == 0 ? (nums2[(totalLength >> 1) - 1] + nums2[totalLength >> 1]) / 2.0 : nums2[totalLength >> 1];
        }
        if (num2Len == 0) {
            return totalLength % 2 == 0 ? (nums1[(totalLength >> 1) - 1] + nums1[totalLength >> 1]) / 2.0 : nums1[totalLength >> 1];
        }
        int nums1Index = 0;
        int nums2Index = 0;
        int[] ints = new int[totalLength];
        // 合并后数组的索引位
        int currIndex = 0;
        while (nums1Index < num1Len && nums2Index < num2Len) {
            if (nums1[nums1Index] < nums2[nums2Index]) {
                ints[currIndex++] = nums1[nums1Index++];
            } else {
                ints[currIndex++] = nums2[nums2Index++];
            }
        }
        // nums1走完了
        if (nums1Index == num1Len) {
            while (nums2Index < num2Len) {
                ints[currIndex++] = nums2[nums2Index++];
            }
        }
        // nums2走完了
        if (nums2Index == num2Len) {
            while (nums1Index < num1Len) {
                ints[currIndex++] = nums1[nums1Index++];
            }
        }
        // 如果合并后数量为偶数个， 如果合并后数量为奇数个
        return totalLength % 2 == 0 ? (ints[(totalLength >> 1) - 1] + ints[totalLength >> 1]) / 2.0 : ints[totalLength >> 1];
    }

    public static void main(String[] args) {
        Hot004FindMedianSortedArrays_H hot004FindMedianSortedArrays_h = new Hot004FindMedianSortedArrays_H();
        System.out.println(hot004FindMedianSortedArrays_h.findMedianSortedArrays(new int[]{1}, new int[]{2, 3, 4}));
    }
}
